#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : SplitArrayFibonacciSequence.py
# @Time    : 2020/12/8 10:13
# @Description:
from typing import List


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        """
        Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence
        [123, 456, 579].

        Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:
            - 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
            - F.length >= 3;
            - and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.
        Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except
        if the piece is the number 0 itself.

        Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

        Example 1:
            Input: "123456579"
            Output: [123,456,579]
        Example 2:
            Input: "11235813"
            Output: [1,1,2,3,5,8,13]
        Example 3:
            Input: "112358130"
            Output: []
            Explanation: The task is impossible.
        Example 4:
            Input: "0123"
            Output: []
            Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.
        Example 5:
            Input: "1101111"
            Output: [110, 1, 111]
            Explanation: The output [11, 0, 11, 11] would also be accepted.
        Note:
            1. 1 <= S.length <= 200
            2. S contains only digits.

        :param S:
        :return:
        """
        ans = []

        def backtrack(index: int):
            if index == len(S):
                return len(ans) >= 3
            curr = 0
            for i in range(index, len(S)):
                if i > index and S[index] == '0':
                    break
                curr = curr * 10 + ord(S[i]) - ord('0')
                if curr > 2 ** 31 - 1:
                    break

                if len(ans) < 2 or curr == ans[-2] + ans[-1]:
                    ans.append(curr)
                    if backtrack(i + 1):
                        return True
                    ans.pop()
                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:
                    break
            return False

        backtrack(0)
        return ans


if __name__ == '__main__':
    solution = Solution()
    # S = "11235813"
    S = "123456579"
    print(solution.splitIntoFibonacci(S))
    print('done')
